#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;
/*
 * 并查集 模板
 *
 *
 * */

int n;
vector<int> father(n);

void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;//自己的父节点等于自己
    }
}

int find(int u) {
    if (u == father[u])
        return u;//如果自己等于自己的父亲直接返回
    else {
        fa[u] = find(father[u]);//当前自己父节点= 最后的那个跟节点
        return father[u];
    }

}

//把v 加入u中
void join(int u, int v) {
    u = find(u);//寻找u的父节点
    v = find(v);//寻找v的父节点

    if (v == u)
        return;

    father[v] = u;
}

// 判断 u 和 v是否找到同一个根，本题用不上
bool same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}



